package link_list

func loopGetIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	loop1, loop2 := detectCycle(headA), detectCycle(headB)
	if loop1 == nil && loop2 == nil {
		return getIntersectionNode(headA, headB)
	}
	if loop1 != nil && loop2 != nil {
		return bothLoop(headA, loop1, headB, loop2)
	}
	return nil
}

func bothLoop(headA, loopA, headB, loopB *ListNode) *ListNode {
	if loopA == loopB {
		p1, p2 := headA, headB
		n := 0
		for p1.Next != loopA {
			p1 = p1.Next
			n++
		}
		for p2.Next != loopA {
			p2 = p2.Next
			n--
		}
		if n < 0 {
			p1, p2 = p2, p1
		}
		n = abs(n)
		for n != 0 {
			p1 = p1.Next
			n--
		}
		for p1 != p2 {
			p1 = p1.Next
			p2 = p2.Next
		}
		return p1
	} else {
		cur := loopA.Next
		for cur != loopA {
			if cur == loopB {
				return loopA
			}
			cur = cur.Next
		}
		return nil
	}
}
